package java_dataLearn;
import java.util.*;
public class Tree {
    public static void main(String[] args) {

    }
}

//n叉树的构造方法
//class Node {
//    public int val;
//    public List<Node> children;
//
//    public Node() {}
//
//    public Node(int _val) {
//        val = _val;
//    }
//
//    public Node(int _val, List<Node> _children) {
//        val = _val;
//        children = _children;
//    }
//};

//class Node {
//    public int val;
//    public Node left;
//    public Node right;
//    public Node next;
//
//    public Node() {}
//
//    public Node(int _val) {
//        val = _val;
//    }
//
//    public Node(int _val, Node _left, Node _right, Node _next) {
//        val = _val;
//        left = _left;
//        right = _right;
//        next = _next;
//    }
//};

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

//class Solution {
//    public List<Integer> postorderTraversal(TreeNode root) {
//        Stack<TreeNode> stack=new Stack<>();
//        List<Integer> ret=new ArrayList<>();
//        //stack.push(root);
//        TreeNode cur=root;
//        TreeNode prev=null;
//        while ( cur!=null || !stack.isEmpty() ){
//            while ( cur !=null ){
//                stack.push(cur);
//                //ret.add(cur.val);
//                cur=cur.left;
//            }
//            TreeNode top=stack.peek();
//            if ( top.right==null || top.right==prev ){
//                ret.add(top.val);
//                stack.pop();
//                prev=top;
//            }else{
//                cur=top.right;
//            }
//        }
//        return ret;
//    }
//}

//class Solution {
//    public String tree2str(TreeNode root) {
//        StringBuilder ret=new StringBuilder();
//        breakTracking(root,ret);
//        return ret.toString();
//    }
//    private void breakTracking(TreeNode root,StringBuilder str){
//        str.append(root.val);
//        if ( root.left!=null ){
//            str.append("(");
//            breakTracking(root.left,str);
//            str.append(")");
//        }else{
//            if ( root.right!=null ){
//                str.append("(");
//                str.append(")");
//            }else{
//                return;
//            }
//        }
//        if ( root.right!=null ){
//            str.append("(");
//            breakTracking(root.right,str);
//            str.append(")");
//        }else{
//            return;
//        }
//    }
//}

//class Solution {
//    public List<List<Integer>> levelOrderBottom(TreeNode root) {
//        return breakTracking(root);
//    }
//    private List<List<Integer>> breakTracking(TreeNode root){
//        LinkedList<List<Integer>> res=new LinkedList<>();
//        if ( root==null ){
//            return res;
//        }
//        Queue<TreeNode> que=new LinkedList<>();
//        que.offer(root);
//        while ( !que.isEmpty() ){
//            int size=que.size();
//            List<Integer> list=new ArrayList<>();
//            while ( size!=0 ){
//                TreeNode node=que.poll();
//                list.add(node.val);
//                if ( node.left!=null ){
//                    que.offer(node.left);
//                }
//                if ( node.right!=null ){
//                    que.offer(node.right);
//                }
//                size--;
//            }
//            res.addFirst(list);
//        }
//        return res;
//    }
//}


//class Solution {
//    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//        if ( root==null ){
//            return null;
//        }
//        if ( root.val==p.val || root.val==q.val ){
//            return root;
//        }
//        TreeNode left=lowestCommonAncestor(root.left,p,q);
//        TreeNode right=lowestCommonAncestor(root.right,p,q);
//        if ( left==null && right==null ){
//            return null;
//        }
//        if ( left!=null && right!=null ){
//            return root;
//        }
//        if ( left==null ){
//            return right;
//        }
//        return left;
//    }
//}

//class Solution {
//    private int i=0;
//    public TreeNode buildTree(int[] preorder, int[] inorder) {
//        return breakTracking(preorder,inorder,0,preorder.length-1);
//    }
//    private TreeNode breakTracking(int[] preorder,int[] inorder,
//                                   int begin,int end){
//        if ( begin>end ){
//            return null;
//        }
//        TreeNode root=new TreeNode(preorder[i]);
//        int idx=findIdx(inorder,preorder[i],begin,end);
//        i++;
//        root.left=breakTracking(preorder,inorder,begin,idx-1);
//        root.right=breakTracking(preorder,inorder,idx+1,end);
//        return root;
//    }
//    private int findIdx(int[] inorder,int key,int begin,int end){
//        for ( int i=begin;i<=end;i++ ){
//            if ( inorder[i]==key ){
//                return i;
//            }
//        }
//        return -1;
//    }
//}

//class Solution {
//    int i=0;
//    public TreeNode buildTree(int[] inorder, int[] postorder) {
//        i=postorder.length-1;
//        TreeNode root=breakTracking(inorder,postorder,0,postorder.length-1);
//        return root;
//    }
//    private TreeNode breakTracking(int[] inorder,int[] postorder,int begin,
//        int end){
//        if ( begin>end ){
//            return null;
//        }
//        TreeNode root=new TreeNode(postorder[i]);
//        int idx=findIdx(inorder,postorder[i],begin,end);
//        i--;
//        root.right=breakTracking(inorder,postorder,idx+1,end);
//        root.left=breakTracking(inorder,postorder,begin,idx-1);
//        return root;
//    }
//    private int findIdx(int[] inorder,int key,int begin,int end){
//        for ( int i=begin;i<=end;i++ ){
//            if ( inorder[i]==key ){
//                return i;
//            }
//        }
//        return -1;
//    }
//}

//class Solution {
//    public TreeNode invertTree(TreeNode root) {
//        breakTracking(root);
//        return root;
//    }
//    private void breakTracking(TreeNode root){
//        if ( root==null ){
//            return;
//        }
//        TreeNode tmp=root.left;
//        root.left=root.right;
//        root.right=tmp;
//        invertTree(root.left);
//        invertTree(root.right);
//    }
//}

//class Solution {
//    public boolean isBalanced(TreeNode root) {
//        int num=checkNum(root);
//        if ( num==-1 ){
//            return false;
//        }
//        return true;
//    }
//    private int checkNum(TreeNode root){
//        if ( root==null ){
//            return 0;
//        }
//        int left=checkNum(root.left);
//        if ( left==-1 ){
//            return -1;
//        }
//        int right=checkNum(root.right);
//        if ( right==-1 ){
//            return -1;
//        }
//        if ( Math.abs(left-right) > 1 ){
//            return -1;
//        }
//        return Math.max(left,right)+1;
//    }
//}

//class Solution {
//    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
//        if ( isSameTree(root,subRoot) ){
//            return true;
//        }else{
//            if ( root!=null ){
//                return isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
//            }else{
//                return false;
//            }
//        }
//    }
//
//    private boolean isSameTree(TreeNode p, TreeNode q) {
//        boolean flag=false;
//        if ( p==null && q==null ){
//            return true;
//        }else if ( p!=null && q!=null ){
//            if ( p.val==q.val ){
//                flag=true;
//            }
//        }else{
//            return false;
//        }
//        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right) && flag;
//    }
//}

//class Solution {
//    public boolean isSameTree(TreeNode p, TreeNode q) {
//        boolean flag=false;
//        if ( p==null && q==null ){
//            return true;
//        }else if ( p!=null && q!=null ){
//            if ( p.val==q.val ){
//                flag=true;
//            }
//        }else{
//            return false;
//        }
//        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right) && flag;
//    }
//}

//class Solution{
//    int getHeight(TreeNode root) {
//        if ( root==null ){
//            return 0;
//        }
//        return Math.max(getHeight(root.left),getHeight(root.right))+1;
//    }
//
//    // 获取叶子节点的个数
//    int getLeafNodeCount(TreeNode root) {
//        int num=0;
//        if ( root==null ){
//            return 0;
//        }
//        if ( root.right==null && root.left==null ){
//            return 1;
//        }
//        return getLeafNodeCount(root.left)+getLeafNodeCount(root.right);
//    }
//}

//leetcode450,二叉搜索树的应用
//class Solution {
//    public TreeNode deleteNode(TreeNode root, int key) {
//        if (root == null) {
//            return null;
//        }
//        if (root.val > key) {
//            root.left = deleteNode(root.left, key);
//            return root;
//        }
//        if (root.val < key) {
//            root.right = deleteNode(root.right, key);
//            return root;
//        }
//        if (root.val == key) {
//            if (root.left == null && root.right == null) {
//                return null;
//            }
//            if (root.right == null) {
//                return root.left;
//            }
//            if (root.left == null) {
//                return root.right;
//            }
//            TreeNode successor = root.right;
//            while (successor.left != null) {
//                successor = successor.left;
//            }
//            root.right = deleteNode(root.right, successor.val);
//            successor.right = root.right;
//            successor.left = root.left;
//            return successor;
//        }
//        return root;
//    }
//}

//class Solution {
//    public TreeNode deleteNode(TreeNode root, int key) {
//
//    }
//    private void delNode(TreeNode root,int key){
//        if ( root.val<key ){
//            if ( root.right==null ){
//                return;
//            }
//            if ( root.right.val!=key ){
//                delNode(root.right,key);
//            }else{
//
//            }
//
//        }
//        if ( root.val>key ){
//            delNode(root.left,key);
//        }
//        if ( root.val==key ){
//            if ( root.left!=null ){
//                //我是将栈中的root中存储的地址改变了还是将堆中的对象改变了
//                root=root.left;
//            }
//        }
//
//    }
//}

//leetcode701
//class Solution {
//    public TreeNode insertIntoBST(TreeNode root, int val) {
//        if ( root==null ){
//            return new TreeNode(val);
//        }
//        func(root,val);
//        return root;
//    }
//    private void func(TreeNode root,int val){
//        if ( root==null ){
//            return;
//        }
//        if ( root.val>val ){
//            if ( root.left!=null ){
//                func(root.left,val);
//                return;
//            }else{
//                TreeNode node=new TreeNode(val);
//                root.left=node;
//                return;
//            }
//        }
//        if ( root.val<val ){
//            if ( root.right!=null ){
//                func(root.right,val);
//                return;
//            }else{
//                TreeNode node=new TreeNode(val);
//                root.right=node;
//                return;
//            }
//        }
//        return;
//    }
//}

//leetcode235
//二叉搜索树写法，利用二叉搜索树有序的特点
//class Solution {
//    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//        if ( root.left==null||root.right==null ){
//            return root;
//        }
//        if ( p.val>q.val ){
//            TreeNode tmp=p;
//            p=q;
//            q=tmp;
//        }
//        TreeNode res=checkNode(root, p, q);
//        return res;
//    }
//    private TreeNode checkNode(TreeNode root,TreeNode p,TreeNode q){
//        if ( root==null ){
//            return null;
//        }
//        if ( root.val>=p.val&&root.val<=q.val ){
//            return root;
//        }
//        TreeNode node=null;
//        if ( root.val>q.val ){
//            node=checkNode(root.left,p,q);
//        }
//        if ( root.val<p.val ){
//            node=checkNode(root.right,p,q);
//        }
//        return node;
//    }
//}

//二叉树写法，时间复杂度较高
//class Solution {
//    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//        TreeNode res=checkNode(root,p,q);
//        return res;
//    }
//    private TreeNode checkNode(TreeNode root,TreeNode p,TreeNode q){
//        if ( root==null ){
//            return null;
//        }
//        if ( root==p||root==q ){
//            return root;
//        }
//        TreeNode left=checkNode(root.left,p,q);
//        TreeNode right=checkNode(root.right,p,q);
//        if ( left==null&&right==null ){
//            return null;
//        }
//        if ( left!=null&&right==null ){
//            return left;
//        }
//        if ( left==null&&right!=null ){
//            return right;
//        }
//        if ( left!=null&&right!=null ){
//            return root;
//        }
//        return null;
//    }
//}

//leetcode236
//回溯对二叉树的应用
//class Solution {
//    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//        TreeNode res=travelVal(root,p,q);
//        return res;
//    }
//    private TreeNode travelVal(TreeNode root,TreeNode p,TreeNode q){
//        if ( root==null ){
//            return null;
//        }
//        if ( root==p||root==q ){
//            return root;
//        }
//        TreeNode left=travelVal(root.left,p,q);
//        TreeNode right=travelVal(root.right,p,q);
//        if ( left==null&&right==null ){
//            return null;
//        }
//        if ( left!=null&&right!=null ){
//            return root;
//        }
//        if ( left==null&&right!=null ){
//            return right;
//        }
//        if ( left!=null&&right==null ){
//            return left;
//        }
//        return null;
//    }
//}

//leetcode108
//class Solution {
//    public TreeNode sortedArrayToBST(int[] nums) {
//        return helper(nums, 0, nums.length - 1);
//    }
//
//    public TreeNode helper(int[] nums, int left, int right) {
//        if (left > right) {
//            return null;
//        }
//
//        // 总是选择中间位置左边的数字作为根节点
//        int mid = (left + right) / 2;
//
//        TreeNode root = new TreeNode(nums[mid]);
//        root.left = helper(nums, left, mid - 1);
//        root.right = helper(nums, mid + 1, right);
//        return root;
//    }
//}

//leetcode 501
//第一次修改
//class Solution {
//    public int[] findMode(TreeNode root) {
//
//    }
//}

//class Solution {
//    List<Integer> answer = new ArrayList<Integer>();
//    int base, count, maxCount;
//
//    public int[] findMode(TreeNode root) {
//        dfs(root);
//        int[] mode = new int[answer.size()];
//        for (int i = 0; i < answer.size(); ++i) {
//            mode[i] = answer.get(i);
//        }
//        return mode;
//    }
//
//    public void dfs(TreeNode o) {
//        if (o == null) {
//            return;
//        }
//        dfs(o.left);
//        update(o.val);
//        dfs(o.right);
//    }
//
//    public void update(int x) {
//        if (x == base) {
//            ++count;
//        } else {
//            count = 1;
//            base = x;
//        }
//        if (count == maxCount) {
//            answer.add(base);
//        }
//        if (count > maxCount) {
//            maxCount = count;
//            answer.clear();
//            answer.add(base);
//        }
//    }
//}
//误
//class Solution {
//    public int[] findMode(TreeNode root) {
//        List<Integer> list=new ArrayList<>();
//        checkNum(root,list);
//        int res=list.get(0);
//        int cnt0=1;
//        int cnt1=0;
//        for ( int i=1;i<list.size();i++ ){
//            if ( list.get(i)==res ){
//                cnt0 ++;
//            }else{
//                cnt1 ++;
//            }
//            if ( cnt1>cnt0 ){
//                res=list.get(i);
//                cnt0=cnt1;
//                cnt1=0;
//            }
//        }
//        return res;
//    }
//    private void checkNum(TreeNode root,List<Integer> res){
//        if ( root==null ){
//            return;
//        }
//        checkNum(root.left,res);
//        res.add(root.val);
//        checkNum(root.right,res);
//        return ;
//    }
//}

//leetcode 530
//class Solution {
//    public int getMinimumDifference(TreeNode root) {
//        List<Integer> list=new ArrayList<>();
//        getList(root,list);
//        int min=Integer.MAX_VALUE;
//        for ( int i=0;i<list.size()-1;i++ ){
//            min=Math.min(list.get(i+1)-list.get(i),min);
//        }
//        return min;
//    }
//    private void getList(TreeNode root,List<Integer> list){
//        if ( root==null ){
//            return ;
//        }
//        getList(root.left,list);
//        list.add(root.val);
//        getList(root.right,list);
//        return ;
//    }
//}

//leetcode98
//class Solution {
//    public boolean isValidBST(TreeNode root) {
//        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
//    }
//
//    public boolean isValidBST(TreeNode node, long lower, long upper) {
//        if (node == null) {
//            return true;
//        }
//        if (node.val <= lower || node.val >= upper) {
//            return false;
//        }
//        return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
//    }
//}
//class Solution {
//    boolean flag=true;
//    public boolean isValidBST(TreeNode root) {
////        if ( root==null ){
////            return flag;
////        }
////        if ( root.left!=null ){
////            if ( root.left.val>=root.val ){
////                flag=false;
////            }
////        }
////        if ( root.right!=null ){
////            if ( root.right.val<=root.val ){
////                flag=false;
////            }
////        }
//////        if ( root.left.val>=root.val||root.right.val<=root.val ){
//////            flag=false;
//////        }
////        isValidBST(root.left);
////        isValidBST(root.right);
////        return flag;
//    }
//    private void breakTrack(TreeNode root,int num){
//        if ( root==null ){
//            return;
//        }
//        if ( root.left!=null ){
//            if ( root.left.val>=num ){
//                flag=false;
//            }
//        }
//        if ( root.right!=null ){
//            if ( root.right.val<=root.val ){
//                flag=false;
//            }
//        }
////        if ( root.left.val>=root.val||root.right.val<=root.val ){
////            flag=false;
////        }
//        isValidBST(root.left);
//        isValidBST(root.right);
//        return;
//    }
//}

//leetcode700
//二叉搜索树
//左子树所有节点的元素值均小于根的元素值；
//右子树所有节点的元素值均大于根的元素值。
//class Solution {
//    public TreeNode searchBST(TreeNode root, int val) {
//        if (root == null) {
//            return null;
//        }
//        if (val == root.val) {
//            return root;
//        }
//        return searchBST(val < root.val ? root.left : root.right, val);
//    }
//}

//leetcode654
//class Solution {
//    public TreeNode constructMaximumBinaryTree(int[] nums) {
//        TreeNode root=new TreeNode();
//        root=creatTree(nums,0,nums.length-1);
//        return root;
//    }
//    private TreeNode creatTree(int[] nums,int idxPre,int idxBack){
//        if ( idxPre>idxBack ){
//            return null;
//        }
//        int idx=checkMax(nums,idxPre,idxBack);
//        TreeNode root=new TreeNode(nums[idx]);
//        root.left=creatTree(nums,idxPre,idx-1);
//        root.right=creatTree(nums,idx+1,idxBack);
//        return root;
//    }
//    private int checkMax(int[] nums,int begin,int end){
//        int max=nums[begin];
//        int idx=begin;
//        for ( int i=begin+1;i<=end;i++ ){
//            if ( nums[i]>max ){
//                max=nums[i];
//                idx=i;
//            }
//        }
//        return idx;
//    }
//}


//leetcode105
//class Solution {
//    public TreeNode buildTree(int[] preorder, int[] inorder) {
//        if ( preorder.length==0||preorder==null ){
//            return null;
//        }
//        Stack<TreeNode> stack=new Stack<>();
//        int inorderIndex=0;
//        TreeNode root=new TreeNode(preorder[0]);
//        stack.push(root);
//        for ( int i=1;i<preorder.length;i++ ){
//            TreeNode node=stack.peek();
//            if ( node.val!=inorder[inorderIndex] ){
//                stack.push(new TreeNode(preorder[i]));
//                node.left=stack.peek();
//            }else{
//                while ( !stack.isEmpty()&&stack.peek().val==inorder[inorderIndex] ){
//                    node=stack.pop();
//                    inorderIndex++;
//                }
//                node.right=new TreeNode(preorder[i]);
//                stack.push(node.right);
//            }
//        }
//        return root;
//    }
//}

//leetcode106
//第二次纠错
//class Solution {
//    //将一棵树看成由很多个根和右子树构成的书
//    public TreeNode buildTree(int[] inorder, int[] postorder) {
//        if ( postorder.length==0||postorder==null ){
//            return null;
//        }
//        Stack<TreeNode> stack=new Stack<>();
//        int inorderIndex=inorder.length-1;
//        TreeNode root=new TreeNode(postorder[postorder.length-1]);
//        stack.push(root);
//        for ( int i=postorder.length-2;i>=0;i-- ){
//            TreeNode node = stack.peek();
//            if ( node.val!=inorder[inorderIndex] ){
//                node.right=new TreeNode(postorder[i]);
//                stack.push(node.right);
//            }else{
//                while ( !stack.isEmpty()&&stack.peek().val==inorder[inorderIndex] ){
//                    node=stack.pop();
//                    inorderIndex--;
//                }
//                node.left=new TreeNode(postorder[i]);
//                stack.push(node.left);
//            }
//        }
//        return root;
//    }
//}
//第一次纠错
//class Solution {
//    //将一棵树看成由很多个根和右子树构成的书
//    public TreeNode buildTree(int[] inorder, int[] postorder) {
//        if ( postorder==null||postorder.length==0 ){
//            return null;
//        }
//        int inorderIndex=inorder.length-1;
//        TreeNode root=new TreeNode(postorder[postorder.length-1]);
//        Deque<TreeNode> stack = new LinkedList<TreeNode>();//双端队列
//        stack.push(root);
//        for ( int i=postorder.length-2;i>=0;i-- ){
//            TreeNode node=stack.peek();
//            if ( inorder[inorderIndex]!=stack.peek().val ){
//                node.right=new TreeNode(postorder[i]);
//                stack.push(node);
//            }else{
//                while ( !stack.isEmpty()&&stack.peek().val==postorder[i] ){
//                    node=stack.pop();
//                    inorderIndex--;
//                }
//                node.left=new TreeNode(postorder[i]);
//                stack.push(node.left);
//            }
//        }
//        return root;
//    }
//}

//class Solution {
//    //将一棵树看成由很多个根和右子树构成的书
//    public TreeNode buildTree(int[] inorder, int[] postorder) {
//        if (postorder == null || postorder.length == 0) {
//            return null;
//        }
//        TreeNode root = new TreeNode(postorder[postorder.length - 1]);
//        Deque<TreeNode> stack = new LinkedList<TreeNode>();//双端队列
//        stack.push(root);
//        int inorderIndex = inorder.length - 1;
//        for (int i = postorder.length - 2; i >= 0; i--) {
//            int postorderVal = postorder[i];
//            TreeNode node = stack.peek();
//            if (node.val != inorder[inorderIndex]) {
//                node.right = new TreeNode(postorderVal);
//                stack.push(node.right);
//            } else {
//                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
//                    node = stack.pop();
//                    inorderIndex--;
//                }
//                node.left = new TreeNode(postorderVal);
//                stack.push(node.left);
//            }
//        }
//        return root;
//    }
//}

//leetcode617
//class Solution {
//    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
//        if (t1 == null) {
//            return t2;
//        }
//        if (t2 == null) {
//            return t1;
//        }
//        TreeNode merged = new TreeNode(t1.val + t2.val);
//        merged.left = mergeTrees(t1.left, t2.left);
//        merged.right = mergeTrees(t1.right, t2.right);
//        return merged;
//    }
//}
//错
//class Solution {
//    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
//        TreeNode root=new TreeNode();
//        breakTracking(root1,root2,root);
//        return root;
//    }
//    private void breakTracking(TreeNode root1,TreeNode root2,TreeNode root){
//        if ( root1==null&&root2==null ){
//            return;
//        }
//        if ( root1==null ){
//            root.val=root2.val;
//            breakTracking(null,root2.left,root);
//            breakTracking(null,root2.right,root);
//        }else if( root2==null ) {
//            root.val=root1.val;
//            breakTracking(root1.left,null,root);
//            breakTracking(root2.right,null,root);
//        }else{
//            breakTracking(root1.left,root2.left,root);
//            breakTracking(root1.right,root2.right,root);
//        }
//    }
//}

//力扣112
//class Solution {
//    boolean flag=false;
//    public boolean hasPathSum(TreeNode root, int targetSum) {
//        if ( root==null ){
//            return flag;
//        }
//        breakTracking(root,targetSum,0);
//        return flag;
//    }
//    private void breakTracking(TreeNode root,int targetSum,int cur) {
//        if ( root.left==null&&root.right==null ){
//            if ( cur+root.val==targetSum ){
//                flag=true;
//            }
//            return;
//        }
//        if ( root.left!=null )
//            breakTracking(root.left,targetSum,cur+root.val);
//        if ( root.right!=null )
//            breakTracking(root.right,targetSum,cur+root.val);
//        return;
//    }
//}

//likou513
//深度优先遍历
//class Solution {
//    int curVal = 0;
//    int curHeight = 0;
//
//    public int findBottomLeftValue(TreeNode root) {
//        int curHeight = 0;
//        dfs(root, 0);
//        return curVal;
//    }
//
//    public void dfs(TreeNode root, int height) {
//        if (root == null) {
//            return;
//        }
//        height++;
//        dfs(root.left, height);
//        dfs(root.right, height);
//        if (height > curHeight) {
//            curHeight = height;
//            curVal = root.val;
//        }
//    }
//}

//class Solution {
//    int max=0;
//    public int findBottomLeftValue(TreeNode root) {
//        //int max=0;//作为最大深度
//        int cur=0;//目前的深度
//    }
//    private int checkLeft(int max,int cur,int res,TreeNode root){
//        if ( root.left==null&&root.right==null ){
//            if ( cur>max ){
//                res=root.val;
//                max=cur;
//            }
//            return res;
//        }
//        if ( cur>max ){
//            max=cur;
//            res=root.val;
//        }
//        cur++;
//        if ( root.left!=null )
//            res=checkLeft(max,cur,res,root.left);
//        if ( root.right!=null )
//            res=checkLeft(max,cur,res,root.right);
//        return res;
//    }
//}

//广度优先遍历
//class Solution {
//    public int findBottomLeftValue(TreeNode root) {
//        Queue<TreeNode> que=new LinkedList<>();
//        que.offer(root);
//        while ( !que.isEmpty() ){
//            int size=que.size();
//            int res=que.peek().val;
//            while ( size!=0 ){
//                TreeNode node=que.poll();
//                size--;
//                if ( node.left!=null ){
//                    que.offer(node.left);
//                }
//                if ( node.right!=null ){
//                    que.offer(node.right);
//                }
//
//            }
//            //如果是最后一层，此时这里的队列应该为空
//            if ( que.isEmpty() ){
//                return res;
//            }
//        }
//        return 0;
//    }
//}

//likou404
//class Solution {
//    public int sumOfLeftLeaves(TreeNode root) {
//        if ( root==null ){
//            return 0;
//        }
//        if ( root.left!=null&&root.left.left==null&&root.left.right==null ){//判断是否为左子叶
//            return root.left.val+sumOfLeftLeaves(root.right);
//        }else{
//            return sumOfLeftLeaves(root.left)+sumOfLeftLeaves(root.right);
//        }
//    }
//}

//likou257
//答案
//class Solution {
//    public List<String> binaryTreePaths(TreeNode root) {
//        List<String> paths = new ArrayList<String>();
//        constructPaths(root, "", paths);
//        return paths;
//    }
//
//    public void constructPaths(TreeNode root, String path, List<String> paths) {
//        if (root != null) {
//            StringBuffer pathSB = new StringBuffer(path);
//            pathSB.append(Integer.toString(root.val));
//            if (root.left == null && root.right == null) {  // 当前节点是叶子节点
//                paths.add(pathSB.toString());  // 把路径加入到答案中
//            } else {
//                pathSB.append("->");  // 当前节点不是叶子节点，继续递归遍历
//                constructPaths(root.left, pathSB.toString(), paths);
//                constructPaths(root.right, pathSB.toString(), paths);
//            }
//        }
//    }
//}

//错误
//class Solution {
//    public List<String> binaryTreePaths(TreeNode root) {
//        List<String> res=new ArrayList<>();
//        if ( root==null ){
//            return res;
//        }
//        List<String> path=new ArrayList<>();
//        breakTracking(root,res,path);
//        return res;
//    }
//    private void breakTracking(TreeNode root,List<String> res,List<String> path){
//        if ( root==null ){
//            path.remove(path.size()-1);
//            List<String> list=new ArrayList<>();
//            list.addAll(path);
//            res.add(list.toString());
//            return;
//        }
////        if ( root==null ){
////            return;
////        }
//        path.add(String.valueOf(root.val));
//        path.add("->");
//        breakTracking(root.left,res,path);
//        path.remove(path.size()-1);
//        breakTracking(root.right,res,path);
//        path.remove(path.size()-1);
//        return;
//    }
//}

//力扣110
//class Solution {
//    public boolean isBalanced(TreeNode root) {
//        if ( root==null ){
//            return true;
//        }
//        return (Math.abs(checkNum(root.left)-checkNum(root.right))<=1)&&isBalanced(root.left)&&isBalanced(root.right);
//    }
//    private int checkNum(TreeNode root){
//        if ( root==null ){
//            return 0;
//        }
//        return Math.max(checkNum(root.left),checkNum(root.right))+1;
//    }
//}

//likou222
//递归遍历，更快和便利
//class Solution {
//    public int countNodes(TreeNode root) {
//        if ( root==null ){
//            return 0;
//        }
//        int left=countNodes(root.left);
//        int right=countNodes(root.right);
//
//        return left+right+1;
//    }
//}

//层序遍历，时间复杂度较大
//class Solution {
//    public int countNodes(TreeNode root) {
//        if ( root==null ){
//            return 0;
//        }
//        Queue<TreeNode> que=new LinkedList<>();
//        que.offer(root);
//        int cnt=0;
//        while ( !que.isEmpty() ){
//            int size=que.size();
//            cnt+=size;
//            while ( size!=0 ){
//                TreeNode node=que.poll();
//                size--;
//                if ( node.left!=null ){
//                    que.offer(node.left);
//                }
//                if ( node.right!=null ){
//                    que.offer(node.right);
//                }
//            }
//        }
//        return cnt;
//    }
//}

//likou101
//class Solution {
//    public boolean isSymmetric(TreeNode root) {
//        return check(root, root);
//    }
//
//    public boolean check(TreeNode p, TreeNode q) {
//        if (p == null && q == null) {
//            return true;
//        }
//        if (p == null || q == null) {
//            return false;
//        }
//        return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
//    }
//}

//likou226
//class Solution {
//    public TreeNode invertTree(TreeNode root) {
//        if ( root==null ){
//            return root;
//        }
//        Queue<TreeNode> que=new LinkedList<>();
//        que.offer(root);
//        while ( !que.isEmpty() ){
//            int size=que.size();
//            while ( size!=0 ){
//                TreeNode node=que.poll();
//                size--;
//                if ( node.left!=null ){
//                    que.offer(node.left);
//                }
//                if ( node.right!=null ){
//                    que.offer(node.right);
//                }
//                TreeNode tmp=node.left;
//                node.left=node.right;
//                node.right=tmp;
//            }
//        }
//        return root;
//    }
//}

//likou111
//class Solution {
//    public int minDepth(TreeNode root) {
//        int cnt=0;
//        if ( root==null ){
//            return cnt;
//        }
//        Queue<TreeNode> que=new LinkedList<>();
//        que.offer(root);
//        while ( !que.isEmpty() ){
//            int size=que.size();
//            if ( size!=0 ){
//                cnt++;
//            }
//            while ( size!=0 ){
//                TreeNode node=que.poll();
//                size--;
//                if ( node.left==null&&node.right==null ){
//                    return cnt;
//                }
//                if ( node.left!=null ){
//                    que.offer(node.left);
//                }
//                if( node.right!=null ){
//                    que.offer((node.right));
//                }
//            }
//        }
//        return cnt;
//    }
//}

//力扣104
//class Solution {
//    public int maxDepth(TreeNode root) {
//        if ( root==null ){
//            return 0;
//        }
//        int cnt=0;
//        Queue<TreeNode> que=new LinkedList<>();
//        que.offer(root);
//        while ( !que.isEmpty() ){
//            int size=que.size();
//            if ( size!=0 ){
//                cnt ++;
//            }
//            while ( size!=0 ){
//                TreeNode node=que.poll();
//                size--;
//                if ( node.left!=null ){
//                    que.offer(node.left);
//                }
//                if ( node.right!=null ){
//                    que.offer(node.right);
//                }
//            }
//        }
//        return cnt;
//    }
//}

//likou116和117
//class Solution {
//    public Node connect(Node root) {
//        if ( root==null ){
//            return root;
//        }
//        Queue<Node> que=new LinkedList<>();
//        que.offer(root);
//        while ( !que.isEmpty() ){
//            int size=que.size();
//            while ( size!=0 ){
//                Node node=que.poll();
//                if ( size==1 ){
//                    node.next=null;
//                }else{
//                    node.next=que.peek();
//                }
//
//                size--;
//
//                if ( node.left!=null ){
//                    que.offer(node.left);
//                }
//                if ( node.right!=null ){
//                    que.offer(node.right);
//                }
//            }
//        }
//        return root;
//    }
//}

//likou515
//class Solution {
//    public List<Integer> largestValues(TreeNode root) {
//        List<Integer> res=new ArrayList<>();
//        if ( root==null ){
//            return res;
//        }
//        Queue<TreeNode> que=new LinkedList<>();
//        que.offer(root);
//        while ( !que.isEmpty() ){
//            int size=que.size();
//            int max=Integer.MIN_VALUE;
//            while (size!=0){
//                TreeNode node=que.poll();
//                size--;
//                if ( node.val>max ){
//                    max=node.val;
//                }
//                if ( node.left!=null ){
//                    que.offer(node.left);
//                }
//                if ( node.right!=null ){
//                    que.offer(node.right);
//                }
//            }
//            res.add(max);
//        }
//        return res;
//    }
//}

//力扣429
//class Solution {
//    public List<List<Integer>> levelOrder(Node root) {
//        List<List<Integer>> res=new ArrayList<>();
//        if ( root==null ){
//            return res;
//        }
//        Queue<Node> que=new LinkedList<>();
//        que.offer(root);
//        while ( !que.isEmpty() ){
//            int size=que.size();
//            List<Integer> path=new ArrayList<>();
//            while ( size!=0 ){
//                Node node=que.poll();
//                size--;
//                path.add(node.val);
//                if ( node.children.size()!=0 ){
//                    for ( int i=0;i<node.children.size();i++ ){
//                        que.offer(node.children.get(i));
//                    }
//                }
////                for (Node child : node.children) {
////                    que.offer(child);
////                }
//            }
//            res.add(path);
//        }
//        return res;
//    }
//}

//class Solution {
//    public List<Double> averageOfLevels(TreeNode root) {
//        List<Double> res=new ArrayList<>();
//        if ( root==null ) {
//            return res;
//        }
//        Queue<TreeNode> que=new LinkedList<>();
//        que.offer(root);
//        while ( !que.isEmpty() ) {
//            int size=que.size();
//            int cnt=size;
//            double sum=0;
//            while ( size!=0 ) {
//                TreeNode node = que.poll();
//                size--;
//                if (node.left != null) {
//                    que.offer(node.left);
//                }
//                if ( node.right != null ) {
//                    que.offer(node.right);
//                }
//                sum+=node.val;
//            }
//            double average=sum/cnt;
//            res.add(average);
//        }
//        return res;
//    }
//}

////likou199
//class Solution {
//    public List<Integer> rightSideView(TreeNode root) {
//        List<Integer> res=new ArrayList<>();
//        if ( root==null ){
//            return res;
//        }
//        Queue<TreeNode> que=new LinkedList<>();
//        que.offer(root);
//        while ( !que.isEmpty() ){
//            int size=que.size();
//            res.add(que.peek().val);
//            while ( size!=0 ){
//                TreeNode cur=que.poll();
//                size--;
//                if ( cur.right!=null ){
//                    que.offer(cur.right);
//                }
//                if ( cur.right!=null ){
//                    que.offer(cur.left);
//                }
//            }
//        }
//        res.add(root.val);
//        while ( root!=null ){
//            if ( root.right!=null ){
//                res.add(root.right.val);
//                root=root.right;
//                continue;
//            }
//            if ( root.left!=null ){
//                res.add(root.left.val);
//                root=root.left;
//                continue;
//            }
//            break;
//        }
//        return res;
//    }
//}

//class Solution {
//    public List<List<Integer>> levelOrderBottom(TreeNode root) {
//        List<List<Integer>> res=new ArrayList<>();
//        Queue<TreeNode> que=new LinkedList<>();
//        Stack<List<Integer>> res0=new Stack<>();
//        if ( root==null ){
//            return res;
//        }
//        que.offer(root);
//        while( !que.isEmpty() ){
//            int size=que.size();
//            List<Integer> path=new ArrayList<>();
//            while ( size>0 ){
//                TreeNode cur=que.poll();
//                size--;
//                path.add(cur.val);
//                if ( cur.left!=null ){
//                    que.offer(cur.left);
//                }
//                if ( cur.right!=null ){
//                    que.offer(cur.right);
//                }
//            }
//            res0.push(path);
//        }
//        while ( !res0.isEmpty() ){
//            res.add(res0.pop());
//        }
//        return res;
//    }
//}

//class Solution {
//    public List<List<Integer>> levelOrder(TreeNode root) {
//        List<List<Integer>> res=new ArrayList<>();
//        if ( root==null ){
//            return res;
//        }
//        Queue<TreeNode> que=new LinkedList<>();
//        que.offer(root);
//        int size;
//        //int cnt=1;
//        while ( !que.isEmpty() ){
//            List<Integer> path=new ArrayList<>();
//            size=que.size();
//            while ( size!=0 ) {
//                TreeNode node = que.poll();
//                path.add(node.val);
//                //cnt--;
//                size--;
//                if (node.left != null) {
//                    que.offer(node.left);
//                }
//                if (node.right != null) {
//                    que.offer(node.right);
//                }
//            }
//            res.add(path);
//        }
//        return res;
//    }
//}

//class Solution {
//    public List<Integer> inorderTraversal(TreeNode root) {
//        List<Integer> result = new ArrayList<>();
//        if (root == null){
//            return result;
//        }
//        Stack<TreeNode> stack = new Stack<>();
//        TreeNode cur = root;
//        while (cur != null || !stack.isEmpty()){
//            if (cur != null){
//                stack.push(cur);
//                cur = cur.left;
//            }else{
//                cur = stack.pop();
//                result.add(cur.val);
//                cur = cur.right;
//            }
//        }
//        return result;
//    }
//}
